package leetcode_core.leetcode_1;

import java.util.HashMap;
import java.util.LinkedHashSet;

/**
 * 即将要维护KV表,KF表,FK表三个映射
 */
class LFUCache {
    HashMap<Integer,Integer> keyToVal;//用于快速获取key=>val的值
    HashMap<Integer,Integer> keyToFreq;//用于快速获取每个值的访问频率
    HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;//用于形成一张表，该表中保存着每个频率所对应的key值
    //LinkedHashSet是链表和哈希集合的结合体，链表不能快速访问链表节点，需要遍历执行，无法达到我们想要快速删除目标值的目的
    //哈希集合中的元素无需，但是可以对元素快速的访问和删除
    int minFreq ;
    //临时维护的变量,用来记录最小的频次
    int cap ;
    //记录LFU缓存的最大容量

    public LFUCache(int capacity) {
        keyToVal = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqToKeys = new HashMap<>();
        this.cap = capacity;
        this.minFreq = 0;//一开始还没有进行访问,故先初始化为0
    }

    public int get(int key) {
        //如果K-V表没有这个key,直接返回-1
        if(!keyToVal.containsKey(key)){
            return -1;
        }
        //否则就是有这个key,返回值之外,还需要对频率进行修改
        increase(key);
        return keyToVal.get(key);
    }

    public void put(int key, int value) {
        //根据算法思路图转换为代码
        if(this.cap<=0){
            return ;
        }
        //1.检查key是否存在,以KV表为准
        if(keyToVal.containsKey(key)){
            //当存在该key的时候
            keyToVal.put(key,value);
            //同时更新频次相关信息
            increase(key);
            return;
        }

        //2.如果key不存在,检查当前容量是否已经满了
        //FK KV KF
        if(keyToVal.size() >= this.cap){
            //如果已经满了,则需要置换
            /**LFU置换算法**/
            //首先获取freq最小的key列表
            LinkedHashSet<Integer> keys = freqToKeys.get(this.minFreq);
            //这些key都是待淘汰的,我们直接将最久没有使用过的key给它淘汰掉
            int oldest = keys.iterator().next();//这里获取的是链式集合头部的元素,越后面的就是越先插入的,淘汰最头部的
            //1.更新频次相关信息=>我们将FK表的信息给更新了先
            keys.remove(oldest);
            if(keys.isEmpty()){//如果删除了这个频次的相关信息后,再也没有这个频次所对应的key表了,直接就直接删除这个key表
                freqToKeys.remove(this.minFreq);
                //此处是否应该需要更新minFreq
                //假如说需要更新minFreq,那么该操作的时间复杂度就不是O(1)了,而是O(n)
                //我们将算法流程走一遍下来哈
                //首先就是什么时候会走这个分支?
                //是当需要进行置换,而且插入一个新key的时候才会被调用
                //那么插入新key的时候,最小的访问频率是不是一定是1?
                //那么就没有必要更新minFreq了
            }
            //更新key-val表,已经预处理完毕
            keyToVal.remove(oldest);
            //更新KF表
            keyToFreq.remove(oldest);
        }
        //否则未满则直接插入即可
        keyToVal.put(key,value);//将对应的值插入到主表
        keyToFreq.put(key,1);//初次访问设置为1
        //同时设置fk表
        freqToKeys.putIfAbsent(1,new LinkedHashSet<>());
        freqToKeys.get(1).add(key);
        //插入新key后的最小freq肯定是1
        this.minFreq = 1;
    }

    void increase(int key){
        //1.修改key=>freq表
        int freq = keyToFreq.get(key);
        keyToFreq.put(key,freq+1);
        //2.修改freq=>key表
        //2.1 将freq=>对应的key删除掉
        LinkedHashSet<Integer> keys = freqToKeys.get(freq);
        keys.remove(key);
        //将key加入到freq+1对应的列表里
        freqToKeys.putIfAbsent(freq+1,new LinkedHashSet<>());
        freqToKeys.get(freq+1).add(key);
        if(keys.isEmpty()){
            //那么就移除这个表
            freqToKeys.remove(freq);
            //如果这个freq恰好就是最小的,已经没有比它更小的了,符合逻辑,删除
            if(freq == this.minFreq){
                this.minFreq++;
            }
        }
    }
}

/**
 * Your leetocde_1.LFUCache object will be instantiated and called as such:
 * leetocde_1.LFUCache obj = new leetocde_1.LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */